package org.usmile.algorithms.leetcode.middle;

/**
 * 318. 最大单词长度乘积
 *
 * 给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 *
 * 示例 1：
 * 输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
 * 输出：16
 * 解释：这两个单词为 "abcw", "xtfn"。
 *
 * 示例 2：
 * 输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
 * 输出：4
 * 解释：这两个单词为 "ab", "cd"。
 *
 * 示例 3：
 * 输入：words = ["a","aa","aaa","aaaa"]
 * 输出：0
 * 解释：不存在这样的两个单词。
 *
 * 提示：
 * 2 <= words.length <= 1000
 * 1 <= words[i].length <= 1000
 * words[i] 仅包含小写字母
 */
public class _0318 {
}

class _0318_Solution {
    public int maxProduct(String[] words) {
        int[] bitMasks = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int bitMask = 0;
            for (char c : words[i].toCharArray()) {
                bitMask = bitMask | (1 << (c - 'a'));
            }

            bitMasks[i] = bitMask;
        }
        int max = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((bitMasks[i] & bitMasks[j]) == 0) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }

        return max;
    }
}

class _0318_Solution1 {
    public int maxProduct(String[] words) {
        int max = 0;
        for (int i = 0; i < words.length; i++) {
            int[] iCount = new int[26];
            for (char c : words[i].toCharArray()) {
                iCount[c - 'a']++;
            }
            loop:
            for (int j = i + 1; j < words.length; j++) {
                for (char c : words[j].toCharArray()) {
                    if (iCount[c - 'a'] != 0) {
                        continue loop;
                    }
                }

                max = Math.max(max, words[i].length() * words[j].length());
            }
        }

        return max;
    }
}